package problem_everyday;

import java.util.ArrayList;
import java.util.List;

public class D2025_07_02_P3333 {




    public int possibleStringCount(String word, int k) {
        if(word.length()==1){
            if(k>1) return 0;
            else return 1;
        }
        List<Integer> counts = new ArrayList<>();
        int count = 0;
        int ones_count = 0;
        for(int i=0; i<word.length()-1; i++){
            if(word.charAt(i) == word.charAt(i+1)){
                count ++;
            } else {
                count ++;
                if(count == 1) ones_count += 1;
                else{
                    counts.add(count);
                }
                count = 0;
            }
        }
        if(word.charAt(word.length()-1) == word.charAt(word.length()-2)){
            counts.add(count+1);
        } else {
            ones_count += 2;
        }
        if(counts.size()==0){
            if(ones_count>=k) return 1;
            else return 0;
        }

        int mod_num = 1000_000_000 + 7;
        long res = 1;
        if(ones_count + counts.size() >= k){
            // 全排列即可
            for(int num :counts){
                res = (res * num) % mod_num;
            }
        } else {
            // 需要搜索组合
            int new_count = k - ones_count;

        }
        return (int)res;
    }

}
